package com.example.lcpractice.lc;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 31. 下一个排列
 * <p>
 * 整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
 * <p>
 * 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
 * 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，
 * 如果数组的所有排列根据其字典顺序从小到大排列在一个容器中， 那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。
 * 如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
 * <p>
 * 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
 * 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
 * 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
 * 给你一个整数数组 nums ，找出 nums 的下一个排列。
 * <p>
 * 必须 原地 修改，只允许使用额外常数空间。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3]
 * 输出：[1,3,2]
 * 示例 2：
 * <p>
 * 输入：nums = [3,2,1]
 * 输出：[1,2,3]
 * 示例 3：
 * <p>
 * 输入：nums = [1,1,5]
 * 输出：[1,5,1]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 100
 */
public class Lc31 {
    public static void main(String[] args) {
//        System.out.println(Arrays.toString(searchRange(new int[]{1, 3, 3, 3, 4}, 3)));
        int[] ints = {3, 2, 1, 2};
        nextPermutation(ints);
        System.out.println(Arrays.toString(ints));
    }

    /**
     * 1、从右往左遍历，找到  i[左] < i+1 [右] 这样才有交换位置变大的机会
     * 2、需要从右往左找略微大于 i[左] 的 确保交换 增量足够小
     * 3、交换位数后，把 i[左] 右边的整个序列反转（降序改升序）  确保  增量足够小
     *
     * @param nums
     */
    public static void nextPermutation(int[] nums) {
        // 逆序数 从倒数第二开始比较
        int reverseNumIndex = nums.length - 2;
        // 条件： nums[reverseNumIndex] >= nums[reverseNumIndex + 1] 左 >= 右
        //  一旦 [reverseNumIndex]左 < [reverseNumIndex+1]右 不执行i--
        // 最大排列: reverseNumIndex=0 仍然   [reverseNumIndex]左 >= [reverseNumIndex+1]右 i刚好 --后变-1
        while (reverseNumIndex >= 0 && nums[reverseNumIndex] >= nums[reverseNumIndex + 1]) {
            reverseNumIndex--;
        }

        if (reverseNumIndex >= 0) {
            int biggerInRightest = nums.length - 1;
            //从右往左， 比逆序数稍微大的数字
            while (biggerInRightest >= 0 && nums[reverseNumIndex] >= nums[biggerInRightest]) {
                biggerInRightest--;
            }
            //交换逆序数 和 稍大数字
            swap(nums, reverseNumIndex, biggerInRightest);
        }
        // 交换整个逆序数右边的序列
        // 如果已经是最大 reverseNumIndex+1=0 交换 0【包括】到 arr.size
        reverse(nums, reverseNumIndex + 1);

    }


    public static void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


}
